/*
 * File: Grasp.c
 *
 * Integrantes:
 * 05-37840 Jormar Arellano
 * 05-38163 Sabrina Fernández
 */

#include "LocalSearch.h"
#include "graph.h"
#include "arraylist.h"
#include "util.h"
#include "Grasp.h"

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int grasp_Giter;
int grasp_Citer;
int grasp_Csize;

void grasp_defaults(){
    grasp_Giter = 4;
    grasp_Citer = 12;
    grasp_Csize = 5;
    grasp_verbose = 0;
}

int grasp_calidad(const ArrayList *s) {
    int i, j, k;
    int count;
    int index;
    ArrayList *particion = NULL;
    Vertex *v1, *v2;

    // Para cada lista de la partición
    for (i=0, count=0; i<s->length; i++) {
        particion = s->data[i];    

        // Busco vecinos
        for (j=0; j<particion->length; j++) {
            v1 = particion->data[j];

            for (k=j+1; k<particion->length; k++) {
                v2 = particion->data[k];

                index = arraylist_index_of(v1->neighbors, compareVertexById, v2);
                if(index>=0){
                    count++;
                }
            }
        }
    }

    return count;
}

int comparePartitionsByLength(ArrayListValue v1, ArrayListValue v2) {
    ArrayList *va = (ArrayList *)v1;
    ArrayList *vb = (ArrayList *)v2;

    // Ordena de MAYOR a MENOR
    if(va->length < vb->length) return 1;
    if(va->length > vb->length) return -1;
    else return 0;
}

ArrayList *improvePhase(Graph *graph, ArrayList *partition) {
    int i, j, n;
    int mejoro;
    ArrayList *vlist, *vaux;

    mejoro = 0;
    do {
        arraylist_sort(partition, comparePartitionsByLength);

        for(j=0; j<partition->length-1; j++) {
            vlist = partition->data[j];

            for(i=0; i<vlist->length; i++) {
                setColor(graph, vlist->data[i], j+1);
            }
        }
        vlist = partition->data[j];
        for(i=0; i<vlist->length; i++) {
            setColor(graph, vlist->data[i], j);
        }
        graph = apply_local_search(graph);
        removeDeadColors(graph);
        n = getTotalColor(graph);

        if( grasp_calidad(graph->Vcolors) == 0 && n<partition->length ){
            vaux = arraylist_new(0);
            for(i=0; i<n; i++) {
                if(graph->Vcolors->length) {
					arraylist_append(vaux, arraylist_copy(graph->Vcolors->data[i]));
                }
            }

            // Liberamos memoria de partition
            for(i=0; i<partition->length; i++) {
                arraylist_free(partition->data[i]);
            }
            arraylist_free(partition);
            partition = vaux;
            mejoro = 1;
        } else {
            mejoro = 0;
        }
    } while(mejoro);

    return partition;
}


Graph *grasp(Graph *graph) {
    int iter, i, ecount, j, e;
    int z, index;
    int minColor;
    ArrayList *vPrim, *vStar, *vRoof, *vi, *vBest;
    ArrayList *U, *C, *CL;
    Vertex *v;

    // Para estadisticas
    long iTotal = 0;
    long cambios = 0;

    minColor = graph->vertex->length;
    vBest = vStar = arraylist_new(0);

    for(iter=0; iter<grasp_Giter; iter++) {
        i=0;
        vPrim = arraylist_copy(graph->vertex);
        arraylist_clear(vStar);

        while(vPrim->length){
            i++;
            ecount = INT_MAX;
            vi = NULL;
            for(j=0; j<grasp_Citer; j++) {
                // vRoof := vPrim
                vRoof = arraylist_new(vPrim->length);
                for(z=0; z<vPrim->length; z++) {
                    arraylist_append(vRoof, vPrim->data[z]);
                    ((Vertex *)vRoof->data[z])->_grasp_mark_u = 0;
                    ((Vertex *)vRoof->data[z])->_grasp_Totalmark_u = 0;
                }

                U = arraylist_new(0);
                C = arraylist_new(0);
                CL = arraylist_new(0);

                while(vRoof->length) {
                    arraylist_clear(CL);
                    if(U->length==0) {
                        // Tomo los ultimos Csize de max degree
                        arraylist_sort(vRoof, compareVertexByNeighbor);
                        for(z=0; z<grasp_Csize && z<vRoof->length; z++) {
                            arraylist_append(CL, vRoof->data[vRoof->length - z - 1]);
                        }
                    } else {
                        // Tomo los ultimos Csize de max degree en U
                        arraylist_sort(vRoof, compareVertexByGrasp_Totalu);
                        for(z=0; z<grasp_Csize && z<vRoof->length; z++) {
                            arraylist_append(CL, vRoof->data[vRoof->length - z - 1]);
                        }
                    }

                    // Selecciono uno al azar
                    v = CL->data[ rand() % CL->length ];
                    arraylist_append(C, v);

                    // V^ := V^ - {v} - N(v)
                    // U  := U + N(v)
                    for(z=0; z<v->neighbors->length; z++) {
                        arraylist_remove(vRoof, arraylist_index_of(vRoof, compareVertexById, v->neighbors->data[z]));
                        arraylist_append(U, v->neighbors->data[z]);
                    }
                    arraylist_remove(vRoof, arraylist_index_of(vRoof, compareVertexById,v));
                }

                // E* = { (u,v) | u,v estan en (V'-C) }. 
                for(z=0, e=0; z<vPrim->length; z++) {
                    v = vPrim->data[z];
                    index = arraylist_index_of(vRoof, compareVertexById, v);
                    if(index<0) {
                        e++;
                    }
                }
                e/=2;
                if(e<ecount) {
                    vi = arraylist_copy(C);
                    ecount = e;
                }
            }
            // V' = V' - Vi
            for(z=0; z<vi->length; z++) {
                arraylist_remove(vPrim, arraylist_index_of(vPrim, compareVertexById, vi->data[z]));
            }
            arraylist_append(vStar, vi);
        }

        vStar = improvePhase(graph, vStar);

        if(vStar->length<minColor) {
            minColor = vStar->length;
            vBest = vStar;
            vStar = arraylist_new(0);
            cambios++;
        }

        if(_steps) waitStep();
        iTotal++;
    }

    // Imprimimos resultados estadisticos
    if(0<grasp_verbose) {
        printf("Reporte de Grasp:\n");
        printf("    >> Colores: %d\n", vBest->length);
        printf("    >> Se realizaron %ld cambios a mejores soluciones\n", cambios);
        printf("    >> Se realizaron %ld iteraciones\n", iTotal);
    }

    // En vBest esta la mejor coloracion obtenida
    ArrayList *vlist;
    for(j=0; j<vBest->length; j++) {
        vlist = vBest->data[j];

        for(i=0; i<vlist->length; i++) {
            setColor(graph, vlist->data[i], j+1);
        }
    }

    return graph;
}
